Many conventional search engine systems typically include one or more search engine devices. A search engine device can include circuitry for performing one or more types of search operations. In a search operation, a comparand (or key) may be compared to multiple entries to see if all or a portion of the key matches an entry. After a search operation, a search engine may give a search result as an output. Typically, a search result may include associated data, or an “index” value that may be used to access associated data.
Search engine devices may take a variety of forms. As but a few of the possible examples, some search engine devices are based on particular types of content addressable memory (CAM) cells. Such CAM cells may include storage circuits integrated with compare circuits. Such storage circuits may be static random access memory (SRAM) type cells or dynamic random access memory (DRAM) type cells, for example. Alternate approaches to search engine devices may include random access memories (RAM) arrays, or the like, with separate matching circuits and/or processes.
Referring now to FIG. 8, a conventional CAM device 800 will be described in more detail. A conventional CAM device 800 may include a CAM array 802, CAM control circuits 804, and CAM register 806.
A CAM array 802 may have a number of entries for storing data values for comparison with a key value. Each entry may include a number of CAM cells. Data may be written to and/or read from entries. In particular embodiments, a key may be compared against multiple data values stored in such entries. If a data value in a CAM entry matches a key, a search hit (match or multiple match) may be indicated. Otherwise a search miss may be indicated. Search hits can be used to generate index values.
A CAM control circuit 804 can take CAM control signals as inputs and generate signals that may control the operation of a CAM array 802 and/or registers 806. Registers 806 can include a number of storage locations that may store key and other values used for search and other operations.
Having described an example of a CAM device, a conventional CAM search operation will now be described. To perform a search operation, a device such as a network processing unit (NPU), may provide a search command to a CAM device 800 on a data/control bus 808. Such a command may include a key value that can be compared to all or a portion of CAM entries within a CAM array 802. In some approaches, a key value may then be stored in registers 806.
A CAM array 802 may generate a result according to a comparison between a key and entries. Results may take various forms, including match results and/or miss results. If a key matches one CAM entry, a single match result may be generated. If a key matches more than one CAM entry, a multiple match result may be generated. If a key does not match any entries, a miss result may be generated. Results may be provided on a result bus 810. A single match result may take various forms. Typically, a single match result may be an index value that points to associated data, or actual associated data itself. Multiple match and/or miss results may be indicated by particular output flags, or the like.
A conventional search engine system that can include conventional CAM devices, such as that shown in FIG. 8, is shown in FIG. 9 and designated by the general reference character 900. In the example of FIG. 9, a search engine system 900 includes “n+1” CAM devices, shown as 902-0 to 902-n. A search engine system 900 may perform search operations in response to commands from a requesting device. In FIG. 9, a requesting device is an NPU 904.
FIG. 9 shows an example of a bus based search engine system. In a bus based search engine system, CAM devices may be commonly connected to a requesting device and to one another by a common bus. Thus, in FIG. 9 CAM devices (902-0 to 902-n) can be commonly connected to each other and to an NPU 904 by a bus 906.
In conventional bus based search engine systems, each CAM device may simultaneously compare a key with entries of its respective CAM array. If a CAM device has a match, the CAM device may forward a match indication (e.g., a flag or the like) to a next, lower priority CAM device. A higher priority CAM device may output a result and a lower priority CAM device can be disabled from outputting data to the common output bus. If, however, a higher priority CAM device does not have a match, such a device may not assert a match indication, and a lower priority CAM device can provide an output result.
A drawback to conventional systems can be limitations in scalability, particularly at a requesting end. That is, conventional approaches may typically include a single requesting device for a given set of CAM devices. In the event an additional requesting device is to be added, some sort of labeling within communications can be employed.
As but one example, in other conventional non-CAM approaches, such as those following Scalable Coherent Interface (SCI), IEEE Standard 1596 or SerialBus IEEE Standard 1394, can dictate that requesting devices issue request packets that can include labels and addresses within request packets. Such labels and/or addresses, referred to herein as stream identifiers, can enable a response to be returned to the appropriate requesting device.
A drawback to conventional approaches that include stream identifiers can be added complexity in a system. Such a system can typically include some sort of mechanism for inserting stream identifiers into request packets. In addition, such a system can typically include some sort of unique-address assignment protocol that determines what stream identifier information is inserted into request packets.
Of course, it is always a goal to increase the efficiency of data transmission in a system. In particular, it is desirable to reduce the amount of “overhead” in a packet. That is, reduce the amount of data that is not payload data in a packet.